package com.example.graph;

import java.util.*;

/**
 * 给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
 * 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
 * <p>
 * 返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入：s = "dcab", pairs = [[0,3],[1,2]]
 * 输出："bacd"
 * 解释：
 * 交换 s[0] 和 s[3], s = "bcad"
 * 交换 s[1] 和 s[2], s = "bacd"
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
 * 输出："abcd"
 * 解释：
 * 交换 s[0] 和 s[3], s = "bcad"
 * 交换 s[0] 和 s[2], s = "acbd"
 * 交换 s[1] 和 s[2], s = "abcd"
 * <p>
 * 示例 3：
 * <p>
 * 输入：s = "cba", pairs = [[0,1],[1,2]]
 * 输出："abc"
 * 解释：
 * 交换 s[0] 和 s[1], s = "bca"
 * 交换 s[1] 和 s[2], s = "bac"
 * 交换 s[0] 和 s[1], s = "abc"
 * <p>
 * 提示：
 * 1 <= s.length <= 10^5
 * 0 <= pairs.length <= 10^5
 * 0 <= pairs[i][0], pairs[i][1] < s.length
 * s 中只含有小写英文字母
 */
public class Leetcode1202_SmallestStringWithSwaps {
    public static void main(String[] args) {
//        String str = "dcab";
//        List<List<Integer>> pairs = new ArrayList<>();
//        List<Integer> lst1 = new ArrayList<>();
//        lst1.add(0);
//        lst1.add(3);
//
//        List<Integer> lst2 = new ArrayList<>();
//        lst2.add(1);
//        lst2.add(2);
//
//        List<Integer> lst3 = new ArrayList<>();
//        lst3.add(0);
//        lst3.add(2);
//
//        pairs.add(lst1);
//        pairs.add(lst2);
//        pairs.add(lst3);

        String str = "dcab";
        List<List<Integer>> pairs = new ArrayList<>();
        List<Integer> lst1 = new ArrayList<>();
        lst1.add(0);
        lst1.add(3);

        List<Integer> lst2 = new ArrayList<>();
        lst2.add(1);
        lst2.add(2);

        List<Integer> lst3 = new ArrayList<>();
        lst3.add(0);
        lst3.add(2);

        pairs.add(lst1);
        pairs.add(lst2);
        pairs.add(lst3);

        System.out.println(new Solution().smallestStringWithSwaps(str, pairs));
    }

    static class Solution {
        /**
         * 并查集解法
         * 因为交换关系具有传递性且可以进行任意次的交换
         * 所以需要先找出同属于一个连通分量的所有字符(使用并查集)
         *
         * 然后把「连在一起」的索引按照字符的 ASCII 值升序排序(分为多组)
         *
         * 最后将所有求得的连通分量重组成字符串
         *
         * @param s
         * @param pairs
         * @return
         */
        public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
            if (s == null || pairs == null || pairs.size() == 0) {
                return s;
            }
            UnionFindSet uf = new UnionFindSet(s.length());

            for (List<Integer> pair : pairs) {
                uf.union(pair.get(0), pair.get(1));
            }
            char[] chars = s.toCharArray();
            Map<Integer, Queue<Character>> map = new HashMap<>();// 以合并后的每个集合的parent节点(字符串索引)为key,所有的元素组成的集合为value
            // 遍历字符串将字符串按照上面的规则完成分组
            for (int i = 0; i < chars.length; i++) {
                map.computeIfAbsent(uf.find(i), key -> new PriorityQueue<>()).offer(chars[i]); //使用优先队列是为了免于排序
            }

//            map.forEach((k, v) -> {
//                System.out.print(k + "-->");
//                while (!v.isEmpty()) {
//                    System.out.print(v.poll());
//                }
//            });

            //重组字符串返回结果
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < chars.length; i++) {
                int root = uf.find(i);
                sb.append(map.get(root).poll());
            }
            return sb.toString();
        }

        private class UnionFindSet {
            int[] parent;
            int[] rank;

            public UnionFindSet(int size) {
                parent = new int[size];
                rank = new int[size];

                for (int i = 0; i < size; i++) {
                    parent[i] = i;
                    rank[i] = 1;
                }
            }

            public int find(int node) {
                if (parent[node] != node)
                    parent[node] = find(parent[node]);

                return parent[node];
            }

            public void union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) {
                    return;
                }

                if (rank[rootX] == rank[rootY]) {
                    parent[rootX] = rootY;
                    // 此时以 rootY 为根结点的树的高度仅加了 1
                    rank[rootY]++;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                    // 此时以 rootY 为根结点的树的高度不变
                } else {
                    // 同理，此时以 rootX 为根结点的树的高度不变
                    parent[rootY] = rootX;
                }
            }
        }
    }
}
